package main

import "fmt"

func main() {
	handArray := []int{4, 5, 2, 7, 9, 3, 5, 7, 9, 4, 2, 2, 1, 5}
	quiksort(handArray, 0, len(handArray)-1)
	fmt.Println(handArray)
}

func quiksort(array []int, left, right int) {
	if right > left {
		mid := partition(array, left, right)
		quiksort(array, left, mid-1)
		quiksort(array, mid+1, right)
	}
}

func partition(array []int, left, right int) int {
	jizhun := array[left]
	for right > left {
		for right > left && array[right] > jizhun {
			right--
		}
		if right > left {
			array[left] = array[right]
			left++
		}
		for right > left && array[left] < jizhun {
			left++
		}
		if right > left {
			array[right] = array[left]
			right--
		}
	}
	array[left] = jizhun
	return left

}
